package algorithm.sorty.sort.compare;

import algorithm.sorty.Sort;
import algorithm.sorty.BinarySearch;

/**
 * @Description: 插入排序
 * @Author Ammar
 * @Create 2023/5/2 05:50
 */
public class InsertionSort<T extends Comparable<T>> extends Sort<T> {

    /**
     * 最初版本
     */
    public void sort1() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            while (cur > 0 && compare(cur, cur - 1) < 0) {
                swap(cur, cur - 1);
                cur--;
            }
        }
    }


    /**
     * 将交换变为挪动
     */
    //@Override
    public void sort2() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            T v = array[cur];
            while (cur > 0 && compare(v, array[cur - 1]) < 0) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = v;
        }
    }

    /**
     * 用二分搜索优化比较部分
     */
    @Override
    public void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            insert(begin, search(begin));
        }
    }

    // 找到index位置元素的待插入位置
    private int search(int index) {
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (compare(array[index], array[mid]) < 0) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }

    // 将source位置的元素插入到dest位置
    private void insert(int source, int dest) {
        T v = array[source];
        for (int i = source; i > dest; i--) {
            array[i] = array[i - 1];
        }
        array[dest] = v;
    }
}
